package doing.normal_001_100;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * longest-palindromic-substring 最长回文子串
 * Example 1:
 * Input: "babad"
 * Output: "bab"
 * Note: "aba" is also a valid answer.
 * <p>
 * Example 2:
 * Input: "cbbd"
 * Output: "bb"
 *
 * @author 大硕
 * 2019-03-19 10:13 PM
 **/
@Slf4j
public class LongestPalindromicSubstring {

    @SuppressWarnings("all")
    public String longestPalindrome(String s) {
        //TODO
        Map<String, String> map = new HashMap<>();
        map.put("k1", "v1");
        return null;
    }

    @Test
    public void test() {
        log.info("result:{}", longestPalindrome("abcbaegefege"));
    }
}
















/*
public String longestPalindrome(String sinput) {
    if(s.length()==0) {
        return "";
    }

    int len = s.length();
    int maxlen = 0;

    String maxStr = s.substring(0,1);

    // NO.1  i j 两个指针，从两边向中间做循环查找 i++, j--
    for(int i=0; i<len; i++){

        for(int j=len-1; j>=i; j--){

            int left = i;
            int right = j;
            int tmplen = 0;

            // NO.2 在任意一个 i, j 的循环体中 判断回文的可能性

            // -> e a b c b a e <-   tmplen += 2
            //   -> a b c b a <-     tmplen += 2
            //     -> b c b <-       tmplen += 2
            //       -> c <-         tmplen += 1
            while (right > left && s.charAt(right) == s.charAt(left)) {
                left ++;
                right --;
                tmplen += 2;
                if (left == right) {
                    tmplen += 1;
                }
            }

            // NO.3 判断回文碰撞
            // 只有满足了回文格式的才会保存回文字符串 maxStr = abcdcba
            // 如果不是回文 就不会保存在这里
            // 判断指针碰撞 left >= right
            if (maxlen < tmplen && left >= right) {
                maxlen = tmplen;
                maxStr = s.substring(i, j + 1);
            }

            // NO.4 当剩余的空间已经不足以超越
            // 说明已经找到的最大回文长度，直接返回不再判断了
            if (maxlen >= len - i) {
                return maxStr;
            }
        }
    }
    return maxStr;
}
*/